def All_cycles(graph, start_vertex):
    def dfs(current, path, visited, current_weight):
        # 현재 노드 처리
        path.append(current)
        visited.add(current)

        # 인접 노드 탐색
        for neighbor, weight in graph[current]:
            if neighbor == start_vertex and len(path) > 2:  # 사이클 발견 (최소 3개 노드)
                cycle_path = path + [start_vertex]
                total_weight = current_weight + weight
                cycles.append((cycle_path, total_weight))
            elif neighbor not in visited:
                dfs(neighbor, path, visited, current_weight + weight)

        # 백트래킹
        path.pop()
        visited.remove(current)

    cycles = []
    dfs(start_vertex, [], set(), 0)
    return cycles

# 가중치 그래프 예시 (인접 리스트 형태)
weighted_graph = {
    'A': [('B', 5), ('C', 2), ('D', 3)],
    'B': [('A', 5), ('C', 1), ('E', 4)],
    'C': [('A', 2), ('B', 1), ('D', 2), ('E', 3)],
    'D': [('A', 3), ('C', 2), ('F', 1)],
    'E': [('B', 4), ('C', 3), ('F', 2)],
    'F': [('D', 1), ('E', 2)]
}

# 'A'에서 시작하는 모든 사이클 찾기
start_vertex = 'A'
all_cycles = All_cycles(weighted_graph, start_vertex)

# 결과 출력
print(f"'{start_vertex}'에서 시작하는 모든 사이클:")
for i, (cycle, total_weight) in enumerate(all_cycles, 1):
    path_str = " → ".join(cycle)
    print(f"> Path.{i:2}: {path_str} :  총길이: {total_weight}")